The CD-ROM and recordable CD, i.e., CD-R, evolved out of the original audio CD. In general, CD-ROMs and CD-Rs are considered to be pervasive and ubiquitous media because of their ability to store large amounts of data, typically over 630 MB of data.
Relatively high error rates are often associated with optical media such as the audio CD (ie., CD Audio), the CD-ROM, and CD-R. In order to address and reduce the relatively high error rates, the CD Audio conventionally included a Cross-Interleaved Reed-Solomon Code (CIRC) to reduce the error rate to an acceptable rate for audio material.
The CD-ROM and CD-R were, in terms of sectoring, designed to overlay the basic physical structure of the CD Audio. For error compensation, the CD-ROM and CD-R retained the Cross-Interleaved Reed-Solomon code but added an additional Reed-Solomon Product Code (RSPC) to accommodate the more stringent error rates required for computer data storage, as specified in the ISO/IEC 10149:1995(E) standard of ISO/IEC, which is incorporated herein by reference.
As computers have become faster, the need for transferring information from the CD-ROM and CD-R at higher rates has increased as well. In order to achieve a higher rate of information transfer, CD-ROM/CD-R drive manufacturers have increased the rotational speed of the CD-ROM/CD-R drives.
Since CD-ROM/CD-R drives are attached to and, therefore, interface with computers, it is generally necessary to have an interface controller to process the data from the CD-ROM/CD-R and deliver the data to an associated computer. Figure la shows a typical system block diagram for an interface controller that is associated with a CD-ROM and a CD-R which is in read mode. A CD-ROM 110 is in communication with a disk interface 112. Since a CD-R is recordable, it has a read mode and a write mode. As such, it should be appreciated that when a CD-R is in read mode, the data flow is from the CD-R to host interface 114, as it is for CD-ROM 110.
Data read from CD-ROM/CD-R 110 is passed through a DRAM 113, which is a memory. Data may be stored in DRAM 113, which is in communication with an error control coding (ECC) arrangement 115 that is used to reduce the error rate associated with data stored in DRAM 113. ECC 115 generally includes a Reed-Solomon decoder, as will be appreciated by those skilled in the art. From DRAM 113, data is provided to a host interface 114.
While the data flow for a CD-R in read mode and a CD-ROM is from the CD-ROM/CD-R to a host, the data flow for a CD-R in write mode, alternatively, is from the host to the CD-R. FIG. 1b is a typical system block diagram for an interface controller that is associated with a CD-R which is in write mode. A host interface 130 provides data to a DRAM 132, which is in communication with an ECC 134. A disk interface 136 reads data from DRAM 132 and writes the data onto a CD-R 138.
Part of the process of passing data between a CD-ROM/CD-R and a host includes ECC operations which are generally used to recover useful data from the CD-ROM/CD-R in the presence of errors. Although the errors can be widely varied, examples of such errors include scratches, fingerprints, and manufacturing imperfections of the physical media.
ECC is generally based on mathematical principles and, as such, entails performing a large number of complex arithmetic computations at high speeds. As the rotational speed of CD-ROM/CD-R drives has increased, the demand placed upon interface controllers has increased as well, since interface controllers must be capable of processing data at much higher rates. The principal impediment to operating the interface controller at high data rates has been the difficulty of performing ECC operations at the increasingly high data rates.
Data on a CD-ROM/CD-R is typically organized as sectors, each of which includes 2352 bytes, as described in the above-mentioned ISO/IEC 10149:1995(E) standard. In general, three types of sectors exist, each with a different data organization. Of the three types of sectors, one type of sector is protected by a Reed-Solomon Product Code. FIG. 2 indicates the physical layout of a sector that can be protected by a Reed-Solomon Product Code or, more generally, an ECC. A sector 202 includes data 204 and parity bytes 206a-b, which will be described in more detail below. As shown, sector 202 includes 2076 bytes of data 204. Data 204 occupy overall bytes "0" through "2063" from the beginning of the data field, while the 172 P-parity bytes 206a occupy bytes "2064" through "2235" from the beginning of the data field, and the 104 Q-parity bytes 206b occupy bytes "2236" through "2339" of the data field. The location of data 204 and parity bytes 206 have, therefore, a relative byte offset from the beginning of the data field. Data 204 is protected by ECC, while parity bytes 206a-b are used for ECC. As will be appreciated by those skilled in the art, the sync bytes of sector 202 are not included in the ECC encoding, and are not protected by ECC.
In a typical system, data from a CD-ROM/CD-R is read into a word-wide dynamic memory (DRAM) using a mapping between memory word addresses and relative byte offsets. Such a mapping is shown in FIG. 3. Memory addresses 210 are mapped into relative byte offsets 212, where byte offsets 212 are divided in terms of even bytes 213 and odd bytes 214.
A CD-ROM/CD-R ECC segments a sector into two separate but identical encodings which separately span even and odd bytes. That is, using the DRAM memory addresses as shown in FIG. 3, all the even bytes can be segregated together and encoded by a Reed-Solomon Product Code, and all the odd bytes can be segregated together and encoded by a Reed-Solomon Product Code, as indicated in FIG. 4. That is, even, or odd, data bytes 220, which are protected by ECC, can be segregated together along with their associated P-parity bytes 222 and Q-parity bytes 224.
As previously mentioned, a CD-ROM/CD-R specifies a Reed-Solomon Product Code. The specification of a Reed-Solomon Product Code implies that there are two dimensions, which are referred to as "P" and "Q." With reference to FIG. 5, the Reed-Solomon Product Code data organization of even or odd bytes, which are taken separately, of a sector will be described. Specifically, the data organization of a Reed-Solomon Product Code will be described in terms of the manner in which ECC encoding is performed. The construction of the Reed-Solomon Product code involves creating a matrix of data 228, which has 43 columns 229 and 24 rows 230. Elements in cells 232 correspond to word, or memory, addresses for DRAM data organization as shown in FIG. 3.
The data in each column 229 includes 24 bytes, and is encoded by a single-error correcting Reed-Solomon code, and two parity bytes for each column 229 are placed in rows 230h and 230i in column 229 over which the encoding has taken place. Each newly formed codeword is a separate P codeword. Therefore, there are 43 such codewords, corresponding to the 43 columns 229. For purposes of explanation, each individual P codeword will referenced as P.sup.i, where i ranges from 0 to 42.
The encoding of individual P codewords represents one dimension of the Reed-Solomon Product Code. The second dimension of the Reed-Solomon Product Code involves encoding data lying along the diagonals of matrix 228. For the second dimension, which encodes Q codewords, the "data," which consists of 43 bytes, includes some of the parity bytes of the P codewords, as will be described in more detail with respect to FIG. 6.
FIG. 6 illustrates the manner in which the Q codewords are typically constructed by presenting two specific Q codewords. FIG. 6 is a partial representation of matrix 228 of FIG. 5. That is, matrix 228' of FIG. 6 is essentially matrix 228 of FIG. 5, without Q-parity rows 230k and 230l. The first Q codeword 240 starts in row 0, column 0 of matrix 228' and proceeds down the diagonal until Q codeword 240 reaches column 25, row 24, at which point Q codeword 240 continues from row 0, column 26 until Q codeword 240 terminates at row 16, column 42. It should be appreciated that parity bytes associated with P codewords in matrix 228', which are located in rows 24 and 25, are also included in Q codeword 240. The two parity bytes for Q codeword 240 are placed in Q-parity positions associated with matrix 228'. That is, Q parity bytes for Q codeword 240 are placed in row 230k (location 1118) and row 2301 (location 1144), at column 229a, as shown in FIG. 5.
Another Q codeword 242 starts in row 20. As before, Q codeword 242 moves down matrix 228'. Q codeword 242 moves from row 20, column 0 at a diagonal until row 25, column 5 is reached. Then, Q codeword 242 continues from row 0, column 6, moving at a diagonal down to row 25, column 31. Q codeword 242 then continues from row 0, column 32 along a diagonal until row 10, column 42 is reached. As was the case for Q codeword 240, P parity bytes are included in Q codeword 242. Specifically, P parity bytes located at row 24, column 4, as well as P-parity bytes at row 25, column 6, P-parity bytes at row 24, column 30 and P-parity bytes at row 25, column 31, are all included as a part of Q codeword 242. The two parity bytes for Q codeword 242 are placed in row 230k (location 1138) and row 2301 (location 1164), of matrix 228, as shown in FIG. 5.
In total, there are 26 Q codewords, corresponding to each of the 26 rows of matrix 228'. That is, the first element of each Q codeword, as for example Q codeword 240, starts in column 0 of each row. The 26 Q codewords which correspond to rows of a matrix is in contrast to the 43 P codewords which correspond to each of the columns of a matrix, as described above with respect to FIG. 5. For purposes of explanation, each individual Q codeword will referenced as Q.sup.j, where j ranges from 0 to 25.
As previously mentioned, each dimension, i.e., P and Q, of the Reed-Solomon Product Code is encoded by a single-error correcting (SEC) Reed-Solomon code. In order to encode the dimensions, a CD-ROM/CD-R typically uses a Galois Field (i.e., GF(2.sup.8)) generated by the following primitive polynomial: EQU p(x)=x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1
where the primitive element of GF(2.sup.8) is: .alpha.=(00000010). The same SEC Reed-Solomon code is used for both the P codewords and Q codewords. The SEC Reed-Solomon code is generated using the following generator polynomial: EQU g(x)=(x+.alpha..sup.1)(x+.alpha..sup.0)
For a typical CD-ROM/CD-R interface controller, the steps for performing error corrections involve first computing the partial syndromes for each P.sup.i codeword and then performing SEC on each P.sup.i codeword, whenever possible. When the partial syndromes are computed, and SEC is performed, each p.sup.i codeword is processed one at a time, and the errored byte corrected in memory. Then, after all the P codewords are processed, the partial syndromes for each Q.sup.i codeword are computed, and SEC is performed whenever possible. As was the case for the P codewords, each Q.sup.i codeword is processed one at a time, and the errored byte is corrected in memory. The partial syndromes for the P codewords and Q codewords are calculated and SEC is performed whenever possible until either all the partial syndromes are zero, indicating no more detectable errors, or a repetition count associated with the computations expires. FIG. 7 illustrates the preceding steps, where the index i refers to the columns, and index j refers references each Q codeword.
A received polynomial r(x) is the combination of an original codeword and any errors which might have been introduced within the original codeword. In other words, r(x)=c(x)+e(x), where c(x) is the originally generated codeword, and e(x) is the error polynomial which represents any error introduced within the original codeword. Since two factors make up the generator polynomial, due to the fact that a SEC Reed-Solomon code is being implemented, two partial syndromes, S.sub.0 and S.sub.1 can be calculated. The two partial syndromes are calculated by evaluating the received polynomial, r(x) , at each of the factors of the generator polynomial g(x), namely .alpha..sup.0 and .alpha..sup.1. As such, the following expressions for partial syndromes S.sub.0 and S.sub.1 can be obtained: EQU S.sub.0 =r(.alpha..sup.0)=c(.alpha..sup.0)+e(.alpha..sup.0) EQU S.sub.1 =r(.alpha..sup.1)=c(.alpha..sup.1)+e(.alpha..sup.1)
By definition, the originally generated codeword c(x) evaluated at .alpha..sup.0 and .alpha..sup.1 are zero, i.e., c(.alpha..sup.0)=0 and c(.alpha..sup.1)=0, since .alpha..sup.0 and .alpha..sup.1 are factors of generator polynomial g(x). As such, partial syndromes S.sub.0 and S.sub.1 can also be expressed as: EQU S.sub.0 =r(.alpha..sup.0)=e(.alpha..sup.0) EQU S.sub.1 =r(.alpha..sup.1)=e(.alpha..sup.1)
In general, the received polynomial, r(x), is represented as follows: EQU r(x)=r.sub.n-1 x.sup.n-1 +r.sub.n-2 x.sup.n-2 +. . . +r.sub.1 x.sup.1 +r.sub.0 x.sup.0
where the r.sub.i are the data from a DRAM and are, therefore, the original data combined with the error data, and n is the length of the codeword. As such, partial syndromes S.sub.0 and S.sub.1 can further be expressed as ##EQU1##
An alternative method of evaluating the received polynomial r(x) is by the use of Horner's rule, which is a recursive multiply and add algorithm, as will be appreciated by those skilled in the art. In this regard, the partial syndrome equations can be rewritten in the following form: EQU S.sub.i =((. . . (r.sub.n-1 .alpha..sup.i +r.sub.n-2) .alpha..sup.i +r.sub.n-3) .alpha..sup.i +. . .+r.sub.1) .alpha..sup.i +r.sub.0
The usual procedure for computing the partial syndromes is to use the circuit in FIG. 8, which directly implements Horner's rule. A partial syndrome calculation circuit 270 includes a separate circuit, as for example circuits 274, 276, for each partial syndrome that is to be calculated. The coefficients of received polynomial r(x) are sequentially transmitted to partial syndrome calculation circuit 270, where the coefficients of received polynomial r(x) are passed through modulo-2 adders 278, 279, which are implemented by exclusive OR circuits. It should be appreciated that adders 278, 279 are generally identical. The output from adder 278 is multiplied by root .alpha..sup.0 280 of generator polynomial g(x), in order to obtain partial syndrome S.sub.0. Likewise, the output from adder 279 is multiplied by root .alpha..sup.1 217 to obtain partial syndrome S.sub.1. Once obtained, the partially computed partial syndromes S.sub.0 and S.sub.1 are clocked into flip-flops 282, 283.
It should be appreciated that substantially all arithmetic operations are over GF(2.sup.8) such that addition is performed modulo 2. Addition is, therefore, implemented by an exclusive or gate, which is denoted by the .sym. symbol. In addition, fixed Galois Field multiplication is implemented as well. The use of the symbol indicates Galois Field multiplication performed in GF(2.sup.8).
Circuit 270 of FIG. 8 relies upon the proper ordering of the elements of the codewords. As such, circuit 270 only serves its intended purpose if the elements clocked into the circuit are in sequential order, from the first element to the last element.
An error correction operation is performed once partial syndromes S.sub.0 and S.sub.1 are calculated. In the event that either partial syndromes S.sub.0 or S.sub.1 are non-zero, then an error has occurred. If a single random error has occurred, then one of the r.sub.i contains the error, where i identifies the relative location within the codeword which is in error. When a single random error has occurred, then partial syndromes S.sub.0 and S.sub.1 can be expressed in terms of the value of the random error and the error location as follows: EQU S.sub.0 =v EQU S.sub.1 =v.alpha..sup.i =S.sub.0.alpha..sup.i
where v is the error value and i is the error location. To isolate the error location i, the following expression can be used: EQU i=log.sub..alpha. (S.sub.1 /S.sub.0)
Once i is determined, the original data can be recovered by adding the value of S.sub.0 to the data read from memory at location "i." This operation is performed modulo-2, as will be appreciated by those skilled in the art.
The coefficients of received polynomial r(x) represent the elements of a codeword. When an error is present, the location of the error is determined by the procedure described above. The locations are represented by elements of GF(2.sup.8), as shown in FIG. 9. As shown, the .alpha..sup.j are labels for the possible error locations of the codeword. If there is an error in r.sub.n-3, for example, the location of the error is referenced as .alpha..sup.2, which is the result that would be obtained by calculating `i` as described above.
An example of a P codeword, located in column 42 of data matrix 228 is shown in FIG. 10. In FIG. 10, a row 290 contains DRAM addresses of bytes which make up the P codeword. Due to the fact that the even bytes and the odd bytes are treated separately, it should be appreciated that FIG. 10 can refer to either even bytes or odd bytes.
A second row 292 refers to each coefficient of a received polynomial. In this case, any r.sub.k could contain an error, in which case the value obtained from the DRAM would be d.sub.k .sym.e.sub.k, where d.sub.k is the original encoded data and e.sub.k is the error pattern introduced. The two parity bytes of the codeword represented in row 290 are located in cells 293, 294. A third row 296 contains labels, which are elements of GF(2.sup.8), that identify each location of the received polynomial r(x) as a solution for a corresponding error location equation.
As previously mentioned, the operation of the partial syndrome calculation circuit of FIG. 8 requires that the data passed into the circuit is in the proper order, i.e., in the same order in which the original data is encoded. In this regard, the data from a DRAM must be read non-sequentially such that the data can correspond to the same order of bytes making up a codeword. This non-sequential access of data is not as efficient as a sequential access of data due to the fact that DRAMs have a mode of operation called Page Mode which allows data to be accessed much faster when the data is located in consecutive locations within the memory. Hence, the calculation of partial syndromes, as discussed above, causes inefficiency in CD-ROM/CD-R interface controllers since a non-sequential access of data requires more memory bandwidth for obtaining the data from the DRAM.
In general, the inefficiency in CD-ROM/CD-R interface controllers can be attributed to two sources. Once source of inefficiency is due to the fact that each data byte generally must be read twice. That is, each data byte must be read once to calculate the P partial syndromes, and a second time to compute the Q partial syndromes. This is due to the fact that partial syndromes for the P codewords are calculated separately from partial syndromes of the Q codewords, although each data byte is simultaneously used to encode both a P codeword and a Q codeword. Another source of inefficiency is that the calculation of the partial syndromes are made by non-sequential accesses such that the faster Page Mode access method cannot be used.
A typical approach to performing the ECC functions also requires that multiple passes be made through memory in order to perform error correction operations, as shown in FIG. 7. In this regard, each iteration pass through memory involves recalculating the partial syndromes, which uses up a considerable amount of memory bandwidth, as mentioned above. One consequence associated with repeated passes through memory is that less memory bandwidth is available for reading additional sectors of data from the CD-ROM/CD-R and for delivering the corrected data to a host, since the DRAM is the central repository.
In general, conventional approaches to performing ECC operations involve two separate passes through memory for each iteration of the correction process to calculate the partial syndromes for each of the P codewords and each of the Q codewords. Multiple iterations are required, thereby leading to additional DRAM memory accesses. Each memory access is a non-sequential access which is much less efficient than using a Page Mode access method. As such, the maximum transfer rate of data from a CD-ROM/CD-R to a host is often limited due to the high DRAM memory bandwidth required by the ECC operations.
For a CD-R, it is requirement for data to be written onto the disk in the same format as for CD-ROM. Hence, it is necessary to generate parity bytes for all of the associated P codewords and Q codewords. In a conventional approach to writing data onto a CD-R, data from a host computer is placed into the DRAM main memory, as described above with respect to FIG. 1b. Once data is placed into the main memory, the EDAC then accesses the data and computes the P parity bytes and Q parity bytes. As was the case for the typical approach taken with respect to a CD-ROM, the individual data making up the codewords for each dimension are accessed in non-sequential fashion, Le., one after the other, such that the appropriate parity bytes are computed during each access. The parity bytes are then written into memory. It should be appreciated that such a process implies making two non-sequential passes through memory.
An example of a standard circuit for generating parity bytes is shown in FIG. 11. Circuit 302 relies upon the proper ordering of the data bytes since the parity bytes are computed in "byte-serial" fashion. Data is passed through an exclusive OR 304, which functions as modulo-two adder. The output from adder 304 is separately multiplied by .alpha.306 and clocked into flip-flop 312. The output from adder 304 is also multiplied by .alpha..sup.25 308, passed through an adder 311, and clocked into flipflop 310.
In circuit 302, the input data, or DataIn 314, comes from DRAM. The bytes in DataIn 314 are clocked into circuit 302 which performs a byte-serial division of the data using the following generator polynomial g(x): EQU g(x)=(x+.alpha..sup.0)(x+.alpha..sup.1)
After the last data byte is inputted to circuit 302, the two flip-flops 310, 312 hold the remainder of the division, which are the parity bytes. The parity bytes can then be written out to the DRAM. The result of the byte-serial division operation is to create, or encode, a Reed-Solomon codeword in systematic form. That is, the byte-serial division allows the original data to be included in the computed codeword, with the parity bytes "tacked on" to the end of the data.
The systematic form of a Reed-Solomon codeword is generally computed as follows: EQU c(x)=(d(x)*x.sup.2 modulo g(x))+d(x)*x.sup.2
where c(x) is the Reed-Solomon codeword, d(x) is the data, and g(x) is the generator polynomial. As shown in the above expression, data d(x) is first pre-multiplied by x.sup.2 and divided by g(x). Then, the results of the pre-multiplication and division are added to d(x)*x.sup.2.
The computation of P and Q codewords associated with writing data onto a CD-R requires two non-sequential passes through memory, as well as separate circuitry that must be used in addition to the syndrome computation circuits.
The maximum transfer rate of data from a CD-ROM/CD-R to a host or from a host to a CD-R is often limited due to the high DRAM memory bandwidth required by the ECC operations. Therefore, as the general demand for high-speed CD-ROM and CD-R is always increasing, what is desired is a method and an apparatus for efficiently implementing ECC without requiring a high DRAM memory bandwidth. Specifically, what is desired is a method and an apparatus for efficiently calculating partial syndromes for use in a Reed-Solomon encoder and decoder.